The present invention relates generally to the field of error correcting for digital information transmission and processing systems and, in particular, to threshold decoders for convolutional and block codes.
Heretofore, convolutionally-coded data transmissions have been decoded by a number of techniques which rely upon digital methods and algorithms for their implementation. The general methods used have been known as Viterbi decoding, conventional threshold decoding and a posteriori probability (APP) decoding. Within these methods, there have been refinements which have improved performance and which have also increased their complexity.
The greatest real-time convolutional coding gains are presently achieved by employing the Viterbi decoding algorithm with soft detection techniques. A Viterbi decoder becomes impractical, however, for code rates greater than about three-quarters (3 information bits out of 4 transmitted bits) and constraint lengths greater than about 10 information bits. Even where practical, the Viterbi decoder is a complex and expensive apparatus.
Conventional threshold decoders utilize hard decisions and are readily implemented with standard digital integrated circuits. The performance of a conventional threshold decoder does not match that of a Viterbi decoder, but the use of a conventional threshold decoder is quite practical for high code rates and very long constraint lengths because the complexity of such a decoder is not as sensitive a function of code rate and constraint length as is a Viterbi decoder. Hard-decision decoding ignores the noise probability distribution in the information channel. As a consequence, the use of hard-decision techniques reduces the possible gain of a decoding method by approximately 2dB.
The use of input data in analog form has been used to calculate non-linear weighting factors which are used to weight parity checks in a method known as a posteriori probability (APP) decoding. The APP method of using probability information in threshold decoding involves formation of hard-decision parity checks obtained by conventional hard-decision threshold decoding.
Approximate APP decoding techniques employing three-bit soft decisions have also been proposed. These digital approaches essentially perform conventional hard-decision threshold decoding. In addition, a reliability estimate assigned to each input bit is used to weight either the conventional parity checks or the threshold value. The approximate APP techniques, while less complicated than the exact APP method, are still considerably more complex than hard-decision threshold decoders. Further, the approximate APP decoders generally require analog-to-digital (A/D) conversion and triple the number of storage registers needed for conventional hard-decision decoding, as well as the necessary circuitry to process the reliability weightings.
Threshold decoders have been divided into two types by J. L. Massey in Threshold Decoding, published by MIT Press, Cambridge, Mass. (1963). The two types of decoding are Type I and Type II. Type I recalculates parity sequences and compares the calculated sequences to those which are received. The results of the compared parity checks are stored in shift registers and are combined to form a set of J orthogonal parity checks for each output pit. A majority decision of the J parity checks is used to determine agreement or disagreement as to the output estimate. In a Type II decoder, the decoder does not recalculate parity, but stores the received information and parity sequences directly in shift registers. Instead of forming J parity checks relative to a single element, J plus 1 estimates of each output bit are obtained and a majority determination is made. In both Type I and Type II cases, J plus 1 is generally equal to the minimum distance property of the code.